# !usr/bin/python
# -*-coding: utf-8-*-
# FileName: 8-8_2.py


MAXX = 3
MAXY = 3
SETPNUM = 6
count = 0
step = -1

def fun(nx, ny):
	global count

	# 到达B点
	if( nx == 0 and ny == 0 ):
		count += 1
		return

	if( nx == 0 ):
		funfun(nx,ny-1)
	elif( ny == 0 ):
		funfun(nx-1,ny)
	else:
		funfun(nx-1,ny)
		funfun(nx,ny-1)

def funfun(nx, ny):
	global count

	# 到达边界
	if( nx == 0 ):
		count += 1
	elif( ny == 0 ):
		count += 1
	else:
		funfun(nx-1,ny)
		funfun(nx,ny-1)


# node = [[1 for i in range(8)] for i in range(8)]
# node经过置1 未经过置0
node = [[0 for i in range(MAXX+1)] for i in range(MAXY+1)]

def funfunfun(x, y):
	# print(x,y)
	global count
	global step
	global MAXX
	global MAXY
	global SETPNUM

	if( x > MAXX or x < 0 or y > MAXY or y < 0):
		return

	if( node[x][y] == 1 ):
		return

	if( x == MAXX and y == MAXY ):
		count += 1
		# print('路径长: ' + str(step))
		return

	node[x][y] = 1
	
	step += 1
	# 超出最小步数则舍弃
	if(step >= SETPNUM):
		# 回溯
		node[x][y] = 0
		step -= 1
		return

	funfunfun(x+1, y)
	funfunfun(x-1, y)
	funfunfun(x, y+1)
	funfunfun(x, y-1)

	# 回溯
	node[x][y] = 0
	step -= 1


count = 0
fun(MAXX, MAXY)
print('fun1: ' +  str(count))

count = 0
funfun(MAXX, MAXY)
print('fun2: ' +  str(count))

count = 0
funfunfun( 0, 0 )
print('fun3: ' +  str(count))

